Simple Distributed Graph Clustering using Modularity and Map Equation

摘要

We study large-scale, distributed graph clustering. Given an undirected,weighted graph, our objective is to partition the nodes into disjoint setscalled clusters. Each cluster should contain many internal edges. Further,there should only be few edges between clusters. We study two establishedformalizations of this internally-dense-externally-sparse principle: modularityand map equation. We present two versions of a simple distributed algorithm tooptimize both measures. They are based on Thrill, a distributed big dataprocessing framework that implements an extended MapReduce model. Thealgorithms for the two measures, DSLM-Mod and DSLM-Map, differ only slightly.Adapting them for similar quality measures is easy. In an extensiveexperimental study, we demonstrate the excellent performance of our algorithmson real-world and synthetic graph clustering benchmark graphs.